﻿#ifndef HASH_BUCKET_HPP
#define HASH_BUCKET_HPP


// 实现一个简易的STL版本的hash table
#include <iostream>
#include <vector>
#include <list>
#include <string>

namespace SFW
{
    using std::vector;
    using std::pair;
    using std::string;
    using std::size_t;

    // 默认哈希函数(这个作用将不同类型的key转换为size_t类型)
    template<class K>
    struct DefaultHashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };


    template<>
    struct DefaultHashFunc<std::string>
    {
        size_t operator()(const std::string& str)
        {
            size_t hash = 0;
            for (auto ch : str)
            {
                hash *= 131;
                hash += ch;
            }

            return hash;
        }
    };


    // hash table 的size
    static constexpr int g_primesNum = 28;
    static constexpr unsigned long g_primes[g_primesNum] {
        53,97,193,389,769,
        1543,3079,6151,12289,24593,
        49157,98317,196613,393241, 786433,
        1572869, 3145739,6291469,12582917,25165843,
        50331653,100663319,201326611,402653189, 805306457,
        1610612741, 3221225473ul, 4294967291ul
    };

    size_t NextSize(size_t oldSize)
    {
        // 找到第一个大于oldSize的质数
        int pos = 0;
        while(g_primes[pos] <= oldSize)
            ++pos;
        return g_primes[pos];
    }

    // hash table node
    template<class T>
    struct HashNode
    {
        HashNode()
            :m_next(nullptr)
        {}

        HashNode(const T& data)
            :m_data(data)
            ,m_next(nullptr)
        {}

        T m_data;
        HashNode<T>* m_next;
    };

    // 迭代器
    template<class K, class T, class ExtractKey, class HashFunc = DefaultHashFunc<K>>
    class HashBucket;

    template<class K, class T, class ExtractKey, class HashFunc = DefaultHashFunc<K>>
    struct HashBucketIterator
    {
        using PNode = HashNode<T>*;
        using HashBucket = HashBucket<K, T, ExtractKey, HashFunc>;
        using Self = HashBucketIterator<K, T, ExtractKey, HashFunc>;

        HashFunc m_hash;
        ExtractKey m_extractKey;
        PNode m_pNode;
        HashBucket* m_pHashBucket;

        HashBucketIterator(PNode node, HashBucket* hashBucket)
            :m_pNode(node)
            ,m_pHashBucket(hashBucket)
        {}

        T& operator*()
        {
            return m_pNode->m_data;
        }

        T* operator->()
        {
            return &m_pNode->m_data;
        }

        Self& operator++(int)
        {
            Self tmp = *this;
            ++(*this);
            return tmp;
        }

        bool operator==(const Self& other)
        {
            return m_pNode == other.m_pNode;
        }

        bool operator!=(const Self& other)
        {
            return m_pNode != other.m_pNode;
        }
        

        Self& operator++() 
        {
            // 如果当前节点有下一个节点，则将当前节点指向下一个节点
            if(m_pNode->m_next)
            {
                m_pNode = m_pNode->m_next;
            }
            else
            {
                // 如果当前节点没有下一个节点，则找到下一个不为空的节点
                size_t hashi = m_hash(m_extractKey(m_pNode->m_data)) % m_pHashBucket->m_bucket.size();
                for(size_t i = hashi + 1; i < m_pHashBucket->m_bucket.size(); ++i)
                {
                    if(m_pHashBucket->m_bucket[i])
                    {
                        m_pNode = m_pHashBucket->m_bucket[i];
                        break;
                    }
                }
            }
            return *this;
        }
    };


    // 哈希桶
    template<class K, class T, class ExtractKey, class HashFunc>
    class HashBucket
    {
    public:
        using Node = HashNode<T>;

        friend struct HashBucketIterator<K, T, ExtractKey, HashFunc>;
        using Iterator = HashBucketIterator<K, T, ExtractKey, HashFunc>;
    private:
        // 哈希函数
        HashFunc m_hash;
        // 从data中取出key
        ExtractKey m_extractKey;
        // 哈希桶
        vector<Node*> m_bucket;
        // 哈希桶的size
        size_t m_size;
    public:
        HashBucket(size_t capacity = 10);
        // 插入
        bool insert(const T& data);
        // 查找
        HashNode<T>* find(const K& key);
        // 删除
        bool erase(const K& key);

        size_t size() const {return m_size;};


        // 迭代器
        Iterator begin()
        {
            for(size_t i = 0; i < m_bucket.size(); ++i)
            {
                if(m_bucket[i])
                    return Iterator(m_bucket[i], this);
            }
            return end();
        }

        Iterator end()
        {
            return Iterator(nullptr, this);
        }
    };

    template<class K, class T, class ExtractKey, class HashFunc>
    HashBucket<K, T, ExtractKey, HashFunc>::HashBucket(size_t capacity)
        : m_bucket(NextSize(capacity))
        , m_size(0)
    {}

    template<class K, class T, class ExtractKey, class HashFunc>
    bool HashBucket<K, T, ExtractKey, HashFunc>::insert(const T& data)
    {
        // 负载因子为1时扩容
        if(m_size == m_bucket.size())
        {
            int newBucketSize= NextSize(m_bucket.size());
            vector<Node*> newBucket(newBucketSize, nullptr);
            // 将旧桶中的元素重新计算hash值，插入到新桶中
            for(int i = 0; i < m_bucket.size(); ++i)
            {
                Node* cur = m_bucket[i];
                while(cur)
                {
                    Node* next = cur->m_next;

                    // 头插入新表中
                    size_t hashi = m_hash(m_extractKey(cur->m_data)) % newBucketSize;
                    cur->m_next = newBucket[hashi];
                    newBucket[hashi] = cur;

                    cur = next;
                }
            }
            m_bucket.swap(newBucket);
        }
        // 1. 计算hashi
        size_t hashi = m_hash(m_extractKey(data)) % m_bucket.size();
        // 2. 头插
        Node* newNode = new Node(data);
        newNode->m_next = m_bucket[hashi];
        m_bucket[hashi] = newNode;
        m_size++;
        return true;
    }

    template<class K, class T, class ExtractKey, class HashFunc>
    HashNode<T>* HashBucket<K, T, ExtractKey, HashFunc>::find(const K& key)
    {
        // 1. 计算hashi
        size_t hashi = m_hash(key) % m_bucket.size();
        // 2. 遍历链表
        Node* cur = m_bucket[hashi];
        while(cur)
        {
            // 找出key值
            if(m_extractKey(cur->m_data) == key)
            {
                return cur;
            }
            cur = cur->m_next;
        }
        return nullptr;
    }

    template<class K, class T, class ExtractKey, class HashFunc>
    bool HashBucket<K, T, ExtractKey, HashFunc>::erase(const K& key)
    {
         // 1. 计算hashi
        size_t hashi = m_hash(key) % m_bucket.size();
        // 2. 遍历链表
        Node* cur = m_bucket[hashi];
        Node* prev = nullptr;
        while(cur)
        {
            // 找到key
            if(m_extractKey(cur->m_data) == key)
            {
                if(prev != nullptr)
                    prev->m_next = cur->m_next;
                else
                    m_bucket[hashi] = cur->m_next;
                
                delete cur;
                --m_size;
                return true;
            }
            prev = cur;
            cur = cur->m_next;
        }
        return false;
    }
}
#endif